package _79

import "sort"

/*
时间复杂度：O(NlogN) 排序所需要的时间复杂度
空间复杂度：O(N) 辅助数组even odd的空间开销

even: 美 [ˈiːvn] 偶
odd: 美 [ɑːd] 奇

先拆分为奇数数组和偶数数据,再排序
*/

func sortEvenOdd(nums []int) []int {
	even, odd := make([]int, 0), make([]int, 0)
	for i, v := range nums {
		if i&1 == 0 {
			even = append(even, v)
		} else {
			odd = append(odd, v)
		}
	}
	sort.Slice(even, func(i, j int) bool {
		return even[i] < even[j]
	})
	sort.Slice(odd, func(i, j int) bool {
		return odd[i] > odd[j]
	})

	// 预分配空间,减少扩容次数
	result := make([]int, len(nums))
	for i, v := range even {
		result[i*2] = v
	}
	for i, v := range odd {
		result[i*2+1] = v
	}
	return result
}
